1. Field of the Invention
The present invention relates to a method for generating an authentic public key of another party of communications.
2. Description of the Prior Art
One of currently available cryptographic techniques which are used to keep data secret, authenticate the other party of communications and make signatures is the public key crypto system. The public key crypto system is best suited to a large scale network having a large number of users, because it involves a small number of sorts of keys to be kept secret. The public key crypto system requires a technique that ensures the completeness of the public key, that is, a technique which assures that data used as the public key of another user party is unmistakably the public key of the other user party.
A first method to ensure the completeness of the public key is provided by a method in which all users, public keys are stored into a public list and managed by a reliable center. In this case, each user can access the public list to see its contents, but only the reliable center that manages the public list can write thereinto. Each user registers its own public key on the public list through the center, and acquires the public key of another user party by referring to the list. However, when this method is applied to a network having a large number of users, many accesses by users concentrate on the public list, burdening the center disadvantageously. Besides, the public key crypto system mentioned herein makes an assumption that the organization managing the public directories is reliable.
A second method to ensure the completeness of the public key is provided by a method in which each user manages its own public key and exchanges its public key with the other party for encrypted communications or authentication of the other party. This method eliminates the need for the public list, thereby dispersing the workload among users. However, the method in turn necessitates a means to ensure that the public key received by one user from the other is the authentic one (assurance of the completeness of the public key). One method to realize this assurance is utilizing a public key identification certificate issued to each user's public key by a reliable organization or center. The public key identification certificate mentioned herein means the signature information, generated by the center on which all users rely, corresponding to each user's identification information ID and public key. Typically, the ID can be any widely known information such as a user's name and address. This method is described below under prior art example 1.
Prior art example 1
FIG. 9 is a chart showing the prior art example described above. Specifically illustrated here is how a center issues a public key identification certificate, based on the ElGamal signature scheme. Element 1 is a user i. Element 2 is a center and element 3 is a user j. Although the ElGamal signature scheme is employed in the example here, any other scheme may be employed to provide a similar construction. The ElGamal signature scheme, a signature scheme based on the difficulty of discrete logarithm problems, is fully discussed in "A Public Key Crypto System and Signature Scheme Based On Discrete Logarithm" (IEEE Trans.on IT, 1985) by T. E. ElGamal. Referring to FIG. 9, the prior art example is described below, organizing the entire procedure into three steps: 1) system setup step carried out by the center 2 for system construction, 2) public key identification certificate issuing step required for a user to subscribe to the system, and 3) public key identification certificate verification step, i.e. public key authenticity verification step carried out to acquire authentic public keys among users.
1) System setup step
(1) The center sets a large prime number q and a primitive root g of the residue-class field with q as a modulus.
(2) The center sets a secret key S, and determines the public key P corresponding to the secret key S according to the equation below: EQU P=g.sup.s mod q [1]
(3) The center notifies each user of (q, g, P).
Note that (mod q) represents an equation in which the residue is determined by dividing by q. Given S, q and g in equation [1], P is easily calculated. If P, q, and g are known, however, determining S becomes more and more difficult as q increases. S is called a discrete logarithm of P wherein q is its modulus and g is its base. Determining S is well known as the discrete logarithm problem.
2) Public key identification certificate issuing step
Described below is a procedure of how an arbitrary user i subscribes to the system.
(1) A user i sets up a secret key xi, and determines its public key yi according to the following equation: EQU yi=g.sup.xi mod q [2]
(Any variable associated with a suffix i means that it is the one for a user i)
(2) The user i notifies the center of its public key yi and its identification information IDi to request the issue of the public key identification certificate with respect to (yi,IDi).
(3) The center verifies that the user who requests the issue of the public key identification certificate is the authentic user i. The explanation of this verification step is skipped, because it is outside the coverage of the present invention.
(4) The center prepares a secret random number ri for each user, one different from user to user. The center determines the public key identification certificate (ti, si) with respect to (yi, IDi) by means of the center's secret key S using the following equations: EQU ti=g.sup.ri mod q [3] EQU si=(yi IDi-S.times.ti)/ri mod (q-1) [4]
where .phi.denotes a concatenation.
(5) The center issues the public key identification certificate (ti, si) to the user i.
3) Public key identification certificate verification step
Described below is a step of how the arbitrary user j gets the authentic public key from the arbitrary user i. Conversely, this step is applied also when the user i gets the authentic public key of the user j. Thus, with each other's authentic public key obtained by both of i and j, it is possible to perform encrypted communications and authentication communications using the public key crypto system therebetween.
(1) The user i notifies the user j of its public key yi and identification information IDi and its public key identification certificate (ti, si) which has been issued by the center in step 2).
(2) The user j checks if the following equation holds good, using public key yi, identification information IDi, and public key identification certificate (ti, si) notified of by the user i: EQU g .sup.yi IDI =P .sup.ti .times.ti .sup.si mod q [5]
The user j receives the public key yi as the authentic public key of user i if equation [5] holds good. If not, the user j discards yi. It should be noted that a set of variables (q, g, P) has been provided by the center in step 1).
This method of verifying the public key identification certificate mentioned above frees each user from accessing the center to get the public key of the other user.
Listed below are traffic from the user i to the user j and the amount of calculation conducted in the calculation process on both users, in the public key identification certificate verification step of the prior art example 1 mentioned above:
Traffic: Approx. 4.times.log z q bits (assume that yi, IDi, ti, si&lt;q)
Process Amount: Amount: Approx. 1.875.times.log z q times of residue of the multiplication calculation process per log .sub.2 q bit width on average
The above method of using the public key identification certificate issued by the center is known for the need to set, for example, 512 or so for log .sub.2 q, in order to assure sufficient security of the secret key xi (thus, in order to present sufficient difficulty in solving the discrete logarithm problem). Substituting 512 for log .sub.2 q results in a traffic of 2048 bits. The overall calculation process amount both on the user i and user j is thus average approx. 960 times of residue of the multiplication calculation process per 512 bit width.
There is another available method which, like the prior art example 1, eliminates the need of the public list and yet allows each user to get the authentic public key from the other user. I call it is a public key generation method. In the other use's public key generation method, each user generates the public key according to the information transmitted by him and the public information of the system. The generated public key of the other user is used, without confirming its authenticity on the spot, to make encryted communications or authentication communication with him. The public key generation method features as follows:
(a) Based on user identification information, a center generates and issues, in advance, the user information to the user. Since the user information has been generated by means of the center's secret key, no user can forge it. The user transmits data to the terminal of the other user, after preparing data according to the user information.
(b) Whether the public key generated by means of data transmitted by the user is authentic or not can be determined later when the public key is used.
The above statement that the user information cannot be forged means that a forger has a difficulty in producing the user information which is required to generate the public key corresponding to the secret key selected by the forger. Even if an attempt is made to use an unauthentic public key, generated from the user information which has been somehow forged, the security of the secret key xi is not endangered because the forger (if more precisely termed, nobody) has no corresponding secret key. This method allows the authenticity of the public key to be indirectly verified. In other words, the authenticity of the public key does not need to be verified in such a direct manner as in the prior art example 1.
Prior art example 2
One of the known public key generation methods is the one proposed in Japanese Laid-Open Patent Publication No. 314586/1988.
The procedure of this method is illustrated in FIG. 10. Referring to FIG. 10, the procedure of this method is described below as prior art example 2. Element 1 is a user i Element 2 is a center and element 3 is a user j.
1) System setup step
(1) The center sets up large secret prime numbers p and q, and determines the product n of both numbers. The center also determines a primitive root g which is common to both one residue-class field provided by modulus p and another residue-class field provided by modulus q.
(2) The center sets up a secret key d, and determines e so that e satisfies the equation: e.times.d=1 mod L, where L is LCM (p-1, q-1), that is, the least common multiple of (p-1) and (q-1). Alternatively, e may be first set up in the above equation.
(3) The center keeps (d, p, q) in secret as the center's secret information, while it notifies each user of (n, e, g).
In order to determine d from public e, we must factorize n into prime factors, p and q, and the larger n, is the more difficult the factorization of n becomes. If, for example, 512 is set for n, the determination of the secret d from the public e is practically impossible.
2) User information issuing step
(1) The user i requests the center to issue the user information, notifying it of its own identification information IDi.
(2) The center verifies that the user who requests the issue of user information is authentically the user i.
(3) Using the secret key d, the center generates the user information: EQU si=IDi .sup.-d mod n [6]
(4) The center delivers the user information si to the user i via a secret communications path.
(5) The user i keeps in secret the user information delivered by the center.
3) Public key generation step
Described below is the procedure where the arbitrary user j generates the public key of the arbitrary user i.
(1) The user i generates random number ri, and then generates transmit data xi below: EQU xi=si.times.g .sup.ri mod n [7]
(2) The user i determines the product of the above random number and the public value e, and keeps the result as the secret key.
(3) The user i sends the transmit data xi along with its identification information IDi to the user j.
(4) Receiving the transmit data xi and the identification information IDi of the user i, the user j performs the following calculation: EQU yi=xi .sup.e .times.IDi mod n [8]
Where,
yi=(si.times.g .sup.ri mod n).sup.e .times.IDi mod n (from equation [7])
=IDi .sup.-1 .times.IDi.times.g .sup.e.ri mod n=g .sup.e.ri mod n (from equation [6] and e.times.d=1 mod L)
This yi can be considered as the public key corresponding to the secret key e.times.ri of the user i in the crypto system based on the discrete logarithm.
Compared with the public key identification certificate method as prior art example 1, the public key generation method as prior art example 2 suffers the following shortcomings:
(a) Since the center generates user's secret information (user information si), the center's authority becomes dominant. The center thus must be perfectly reliable.
(b) For the center to deliver the user information to the user in (4), step 2), a secret communications path is required between the center and the user. This requires in turn, for example, an IC card to be used as the medium for delivery.
When the public key is generated in the public key generation method in the prior art example 2, traffic between the user i and the user j, and the amount of calculation conducted in the calculation process on both users, in the public key generation step are listed below. In this case, since the public key e of the center can be decreased down to 3 with its security still maintained, the number of iteration of residue of the multiplication calculation process in power operation using e as exponent is several times (herein .alpha. times). EQU Traffic: 2.times.log .sub.e n bits (where Xi, IDi&lt;n)
Process Amount: (1.5.times.log .sub.2 n+.alpha.) times of residue of the multiplication calculation process per log .sub.2 n bit width on average
The above method is known for the need to set, at least, 512 bits or so for log .sub.2 n, in order to ensure sufficient security, that is, in order to present sufficient difficulty in solving the factoring problem. Substituting 512 for log .sub.2 n results in a traffic of 1024 bits and an overall amount of 768 times of residue of the multiplication calculation process per 512 bit width on average.
By the way, in the prior art examples 1 and 2 shown above, the center can easily commit wrongdoing, as described below, if it so intends. In the prior art example 1, the center sets up for the user i a false secret key and public key (xi', yi'), and the center by itself then issues this public key identification certificate (ti', si') with respect to this yi, and the identification information IDi for the user i. The center then can disguise itself as the user i by notifying a third user of (yi', IDi, ti', si'). In the prior art example 2, the center knows the secret user information of the arbitrary user i. Thus, using the user information, the center can produce transmit data xi',and notifies a third user of (xi',IDi) so that it can disguise itself as the user i.
Against this, there may be another method in which a plurality of centers are established so that wrongdoing cannot be committed unless all the centers cooperate together. Described below is a prior art 3, for example, where a plurality of centers are provided in the prior art example 1. For simplicity of description, only two centers are employed here. The signature scheme which the centers use to issue the public key identification certificate is the ElGamal signature scheme as in the prior art example 1.
Prior art example 3
FIG. 11 shows the construction of the prior art example 3. Referring to FIG. 11, the procedural steps are described below. A first center (hereinafter, center 1) is indicated at 11. A second center (hereinafter, center 2) is indicated at 12. A user i and a user j are indicated at 13 and 14, respectively.
1) System setup step
(1) Both centers 1 and 2, in cooperation, set up a large prime number q and a primitive root g of the residue-class field with q as modulus.
(2) The centers 1 and 2 independently produce secret keys S1 and S2, respectively, and keep them in secret to each other. The centers 1 and 2 determine public keys P1 and P2, respectively, by the following equations:
(Center 1) EQU P1=g .sup.a1 mod q [9]
(Center 2) EQU P2=g .sup.a2 mod q
(3) The centers 1 and 2 notify each user of (q, g, P1, P2).
2) Public key identification certificate issuing step
(1) The user i sets up a secrete key xi, and determines the public key yi with respect to it, according to the following equation: EQU yi=g .sup.xi mod q [10]
(2) the user i notifies both the center 1 and the center 2 of the public key yi and the identification information IDi of the user i, and requests both centers to issue the public key identification certificates with respect to (yi, IDi).
(3) Each center verifies that the user who requests the issue of the public key identification certificates is the authentic user i. The explanation of this verification step is skipped.
(4) The centers 1 and 2 independently generate random number ri 1, ri 2, and then determine public key identification certificates (ti1, si1) and (ti2, si2), respectively, according to the following equation, where symbol denotes a concatenation.
(Center 1) EQU ti1=g .sup.ri1 mod q [11] EQU sil=(yi IDi-S1.times.ti1)/ri1 mod (q-1)
(Center 2) EQU ti2=g .sup.ri2 mod q EQU si2=(yi IDi-S2.times.ti2)/ri2 mod (q-1)
(5) The centers 1 and 2 issue the public key identification certificates (ti1, si1) and (ti2, si2), respectively, to the user i.
3) Public key authenticity verification step
(1) The user i notifies the user j of the public key yi, the identification information IDi and the public key identification certificates (ti1, si1) and (ti2, si2).
(2) The user j checks to see if both equations below hold good with respect to the public key yi, identification information IDi, and public key identification certificates (ti1, si1) and (ti2, si2) notified of by the user i: EQU g .sup.ri IDi =P1 .sup.ti 1.times.ti1 .sup.si1 mod q [12] EQU g .sup.yi IDi =P2 .sup.ti2 .times.ti2 .sup.si2 mod q
The user j receives yi as the authentic public key of the user i if both equations [12] hold good. If either of both equations [12] fails to hold good, the user j discards the public key yi. It should be noted that a set of variables (q, g, P1, P2) is the information publicly provided by each center.
With no knowledge of the secret keys of the centers, each user can hardly generate the public key identification certificates (ti1, si1) and (ti2, si2) that satisfy equations [12]. Unlike the prior art examples 1 and 2, one center alone is unable to commit wrongdoing even if it so intends, in this method. For example, if center 1 intends to disguise itself as the user i, since the center 1 has no knowledge of the secret key S2 of the center 2, it cannot forge the public key identification certificate (ti2, si2) to be issued by the center 2, and the second one of the equations [12] fails to hold, and the wrongdoing can be detected at the user j side. In other words, to make false public key identification certificates for any wrongdoing, both centers need to cooperate. Whereas the number of centers has been assumed here to be two to simplify the description, establishing more centers will make it practically impossible for an individual center to commit wrongdoing.
In the above-described step of the prior art example 3 for verifying the public key identification certificate, traffic between users and the amount of calculation conducted in the calculation process on users are listed below in the case that the number of centers is N. EQU Traffic: (2N+2).times.log .sub.2 q bits
Process Amount: Approx. 1.875.times.N.times.log .sub.2 q times of residue of the multiplication calculation process per log .sub.2 q bit width on average
Substituting 512 for log .sub.2 q, as in the prior art example 1, results in a traffic of (2N+2).times.512 bits. The overall calculation amount processed by users is thus N .times.960 times or so of residue of the multiplication calculation process per 512 bit width on average. Consequently, in the prior art example 3, if the number of centers N is increased to reinforce the security against the wrongdoing which is possible if all the centers cooperate, traffic and calculation amount of the users will also increase proportionately.
Although the prior art example 3 described above has such a construction that the prior art example 1 is extended to involve a plurality of centers, the prior art example 2 may also be extended to a version which has a plurality of centers. In this case, also as in the prior art example 3, if the number of centers are increased to reinforce the security, traffic and calculation amount of the users will increase proportionately.
As already described, compared with the public key identification certificate method in the prior art example 1, the public key generation method in the prior art example 2 suffers the following two shortcomings: First, since the center generates the user's secret key, the center should be completely reliable. Second, for the center to deliver user information to a user, a secret communications path such as an IC card needs to be used as the medium for delivery between the center and the user.
By establishing a plurality of centers, the prior art example 1 (and the prior art example 2, as well) can be extended to a construction which helps avoid wrongdoing by any center, as exemplified by the prior art example 3. Establishing a plurality of centers makes it impossible for each center alone to commit wrongdoing, except for cooperation of all the centers for the wrongdoing. In the prior art example 3 or an extended version of the prior art 2, increasing the number of centers to reinforce the security in case that all centers may cooperate increases proportionately traffic and process amount of calculation of the users.